\section{Related Work}
This section discusses different directory designs for CMP. 
Shadow tags duplicate all the tags present in the private cache,
and construct the sharing vector by looking up the tags when
accessed. The design is simple in concept, and works well in
current designs including SUN Niagara2~\cite{niagara2}. We have shown however that using the techniques describe in this paper we can improve by a factor of 5-6$\times$ for small multicore chips and by upto 10$\times$ for large multicore chips. The bigger challenge is that it requires a energy intensive associative search to construct the sharing pattern.


Tagless directory~\cite{zebchuk-micro-2009} uses bloom filters to map
the tags in each cache set. Therefore tagless directory concisely
summarizes the tags for each set in every core and completely
eliminates the associative search on lookups.  Overall it reduces storage 
compared to shadow tags by a factor of the number of ways in the L1 cache. 
The scaling benefits are limited for large multicores since it does not consider 
optimizing the sharing patterns per bloom filter bucket.  With the increase 
in number of cores, the sharing vector becomes a significant area overhead.


% \sys\ optimizes the tagless system and the coherence directory size
% is a function of the number of sets in the L1 and number of unique
% sharing patterns possible in a target application. This enables it to
% achieve significant benefits over tagless for large
% multicores. Tagless grows as a function of the number of
% sets in the L1 and number of cores in the system. 


%Shadow tags are the most basic form of coherence
%directory which grows with L1 cache size (sets and ways) and number
%of cores in the system. 
Directory cache~\cite{tag_dir,acacio_level} limits the size of the
directory by restricting the number of blocks which the directory
holds the sharing information. With this limitation, if one block is
not present in the directory cache, either all the shared copies have
to be invalidated, or the cache block must be defaulted to shared by
all the processors. Cuckoo directory~\cite{cuckoo-dir} uses improved
hashing algorithm to eliminate associativity related tag evictions in
the directory cache, however still experiences the same effect under
misses. Other proposals try to combine the small directory cache with
the larger in-memory directory~\cite{tag_dir,waypoint}. Such designs
essentially emulate a big directory cache, but they require complex
protocol extensions that touch off-chip metadata, and some directory
accesses will suffer from long latencies.



Full map directory~\cite{Censier_dir} is a simple solution for CMPs
with inclusive shared cache. The bit vector indicating the sharers is
associated with the cache line at the shared cache. Full map directory
also imposes significant storage penalty because the shared cache
included is usually much larger (54MB on the latest Itanium) and
includes lines that are not even cached. SPACE~\cite{zhao-pact-2010}
sought to optimize full map by making the observation that many
entries in the shared cache store redundant patterns.  It decouples
the sharing pattern from directory entries, and only represent
patterns present in the application. Each cache block in the inclusive
cache includes a pointer to the pattern table. Unfortunately, even
uncached blocks include the pointer and this leads to significant
overhead over shadow tag-based approaches.



Coarse vectors~\cite{Gupta90reducingmemory,simoni_thesis}, sharer
pointers ~\cite{sgi_origin,limited-pointer-dir}, and segmented
vectors~\cite{Choi99segmentdirectory} on the other hand all try to
compressing the sharing vector using more compact encodings. Based on the encoding type, these compressed directory could only represent limited
number of sharing patterns, and introduces significant false positives
for other patterns. Under these certain adversarial patterns, such
designs would always perform poorly with the encoding fixed at design
time.

Overall, \sys\ is agnostic to the type of shared cache (inclusive or exclusive), 
affords significant compression over the previously known best approach, tagless, and 
scales based on application's coherence requirements.
